package _11_整理题目._2_二叉树_递归_dfs_bfs._遍历;

import org.junit.Test;
import util.TreeNode;

import java.util.ArrayList;
import java.util.List;


/**
 * 分别按照二叉树先序，中序和后序打印所有的节点。
 * 输入   {1,2,3}
 * 输出   [[1,2,3],[2,1,3],[2,3,1]]
 * 
 * 思路：
 *      先写出三种遍历的递归实现 每个结果各自存到一个 ArrayList<Integer> 中
 *      转换每个 ArrayList<Integer> 为 int[] 并返回
 *      设置一个 int[3][] 接收 返回的 int[]
 *
 */
public class _011_实现二叉树三种遍历 {
    
    private List<Integer> preList = new ArrayList<>();
    private List<Integer> inList = new ArrayList<>();
    private List<Integer> postList = new ArrayList<>();
    
    private void preOrder(TreeNode root, List<Integer> list) {
        if(root==null) return;
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
    
    private void inOrder(TreeNode root, List<Integer> list) {
        if(root==null) return;
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
    
    private void postOrder(TreeNode root, List<Integer> list) {
        if(root==null) return;
        postOrder(root.left, list);
        postOrder(root.right, list);
        list.add(root.val);
    }
    
    private int[] toIntArray(List<Integer> list) {
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    public int[][] threeOrders (TreeNode root) {
        int[][] result = new int[3][];
        preOrder(root, preList);
        inOrder(root, inList);
        postOrder(root, postList);
        result[0] = toIntArray(preList);
        result[1] = toIntArray(inList);
        result[2] = toIntArray(postList);
        return result;
    }
    
    @Test
    public void main() {
        Integer[] input = new Integer[] {1, 2, 3, 4, 5, 6, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        int[][] array = threeOrders(root);
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
